/*
	解法：滑动窗口遍历整个数组 + 哈希表（unordered_map）记录水果种类
	为什么这样想：连续子数组问题 + 条件约束，滑动窗口是标准解法。
				  统计水果的种类个数 + 每种数量，考虑unordered_map容器存储。
	时间复杂度：O(n) 空间复杂度：O(1)
 */
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution 
{
public:
	int totalFruit(vector<int>& fruits) 
	{
		unordered_map<int, int> basket;  // 统计窗口内水果种类及数量
		int left = 0;
		int maxLen = 0;
		
		for (int right = 0; right < (int)fruits.size(); right++) 
		{
			basket[fruits[right]]++;
			
			while (basket.size() > 2)	//一旦窗口不合法（这里就是“多于 2 种水果”），就要收缩左边界 left，直到窗口重新合法（≤ 2 种水果）
			{
				basket[fruits[left]]--;
				if (basket[fruits[left]] == 0) 
				{
					basket.erase(fruits[left]);
				}
				left++;
			}
			
			maxLen = max(maxLen, right - left + 1);
		}
		
		return maxLen;
	}
};

int main() 
{
	Solution sol;
	int n;
	cout << "请输入数组长度 n: ";
	cin >> n;
	
	vector<int> fruits(n);
	cout << "请输入 " << n << " 个整数，以空格分隔: ";
	for (int i = 0; i < n; i++) 
	{
		cin >> fruits[i];
	}
	
	int result = sol.totalFruit(fruits);
	cout << "最多可以采的树数: " << result << endl;
	
	return 0;
}

